#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <unistd.h>
#include <time.h>
#define MAXSIZE 26 

/*
 *global variables
 */
int buf[MAXSIZE];
typedef struct {
	unsigned int weight;
	unsigned int parent, lchild, rchild;
} HTnode, *HuffmanTree;
typedef char ** HuffmanCode;
HuffmanTree HT = NULL;
HuffmanCode HC = NULL;
int numofCode = 0;
char *codebuf;
struct timeval start, end;

void quicksort(char *array)
{

}
void Select(HuffmanTree HT, int n, int *lhs, int *rhs)	
{
	int i;
	int min, sec_min;
	int min_index, sec_min_index;
	min = sec_min = 1 << 30;
	for (i = 1; i <= n; i++) 
		if (HT[i].weight != 0 && HT[i].weight < min &&
		    HT[i].parent == 0) {
			min = HT[i].weight;		
			min_index = i;
		}
	
	for (i = 1; i <= n; i++) 
		if (HT[i].weight != 0 && HT[i].weight < sec_min &&
		    HT[i].parent == 0 && i != min_index) {
			sec_min = HT[i].weight;		
			sec_min_index = i;
		}
	*lhs = min_index;
	*rhs = sec_min_index;
}

void HuffmanCompress(int *w, int n) 
{
	int i, start, c, m, f;
	int codeindex;
	char *cd;
	int s1, s2;
	HuffmanTree p;

	if (n <= 1) 
		return;
	m = 2*n - 1;
	HT = (HuffmanTree) malloc((m+1) * sizeof(HTnode));
	for (p = HT+1, i = 1, codeindex = 0; i <= n; ++w, ++codeindex) {
		if (*w != 0) {
			p->weight = *w;
			p->parent = 0;
			p->lchild = 0;
			p->rchild = 0;
			codebuf[i-1] = 'a' + codeindex; 
			++i;
			++p;
		}
	}
	for (; i <= m; ++i, ++p) {
		p->weight = 0;
		p->parent = 0;
		p->lchild = 0;
		p->rchild = 0;
	}
	for (i = n+1; i <= m; ++i) {
		Select(HT, i-1, &s1, &s2);	
		HT[s1].parent = i; 	
		HT[s2].parent = i;
		HT[i].lchild = s1;  
		HT[s2].rchild = s2;
		HT[i].weight = HT[s1].weight + HT[s2].weight;
	}

	// get Huffman code from leaf to root.
	HC = (HuffmanCode) malloc((n+1) *sizeof(char *));
	cd = (char *) malloc(n * sizeof(char));
	cd[n-1] = '\0';
	for (i = 1; i <= n; i++) {
		start = n-1;
		for (c = i, f = HT[i].parent; f != 0; c = f, f = HT[f].parent) { 
			if (HT[f].lchild == c)	
				cd[--start] = '0';
			else 
				cd[--start] = '1';
		}
		HC[i] = (char *) malloc((n-start) * sizeof(char));
		strcpy(HC[i], &cd[start]);
	}
	free(cd);
}

void HuffmanDepress()
{

}

void usage()
{
	fprintf(stderr, "usage: ./huffman filetocompress filecompress depressfile\n");
}

void config(int argc, char **argv)
{
	FILE *fd;
	char readchar;
	int i;
	if ((fd = fopen(argv[1], "r")) < 0) {
		fprintf(stderr, "open file error!\n");	
		exit(-1);
	}	
	while ((readchar = fgetc(fd)) != EOF) {
		buf[readchar-'a'] += 1;
	}
	for (i = 0; i < MAXSIZE; i++)
		if (buf[i] != 0) 
			numofCode++;			
	codebuf = (char *) malloc((numofCode+1) * sizeof(char));
	fclose(fd);
}

void clean()
{
	int i;
	if (HT) 
		free(HT);
	if (codebuf)
		free(codebuf);
	for ( i = 1; i <= numofCode; i++) 
		if (HC[i] != NULL)
			free(HC[i]);
	if (HC) 
		free(HC);
}

void writeToFile(char *path)
{
	int i;
	FILE *fd;
	if ((fd = fopen(path, "w+")) < 0) {
		fprintf(stderr, "fopen failed\n");	
		exit(-1);
	}
	for (i = 1; i <= numofCode; i++) {
		fprintf(fd, "%c:\t%s\n", codebuf[i-1], HC[i]);	
	}
	fclose(fd);
}

int main(int argc, char *argv[])
{
	gettimeofday(&start, NULL);

	atexit(clean);
	
	if (argc != 3) {
		usage();	
		exit(-1);
	}
	config(argc, argv);
	HuffmanCompress(buf, numofCode);
	writeToFile(argv[2]);

	gettimeofday(&end, NULL);
	printf("total time: %ld s %f ms\n", 
			end.tv_sec-start.tv_sec, (end.tv_usec-start.tv_usec)/1000.0
	);
	return 0;
}
